package com.zxy.leetcode._00000_00099._00010_00019;

import com.zxy.leetcode.common.ListNode;
import com.zxy.leetcode.common.ListNodeHelper;

/**
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 *
 * 删除链表的倒数第N个节点
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 说明：
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 * 你能尝试使用一趟扫描实现吗？
 */
public class Test00019 {

    public static void main(String[] args) {
        Test00019 test = new Test00019();

        ListNode head = ListNodeHelper.build(10);
        ListNodeHelper.print(head);

        head = test.removeNthFromEnd(head, 1);
        ListNodeHelper.print(head);

        head = test.removeNthFromEnd(head, 9);
        ListNodeHelper.print(head);
    }

    // 两次循环了，没完成进阶
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) {
            return head;
        }

        ListNode node = head;
        int count = 0;
        while (node != null) {
            count++;
            node = node.next;
        }

        if (n == count) {
            return head.next;
        }

        node = head;
        int index = 0;
        while (node != null) {
            // 下一个节点是要被删除的
            if (index + 1 == count - n) {
                node.next = node.next.next;
                break;
            }

            node = node.next;
            index ++;
        }

        return head;
    }

    /*
    一次循环解决的方案，来源
    https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/dong-hua-tu-jie-leetcode-di-19-hao-wen-ti-shan-chu/
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode slow = head;
        ListNode fast = head;
        for(int i=0;i<n;i++){
            fast = fast.next;
        }
        while(fast!=null){
            pre = pre.next;
            slow = slow.next;
            fast = fast.next;
        }
        pre.next = slow.next;
        return dummy.next;
    }
}
